package com.mrl.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰表达式（后缀表达式）的求解
 *
 * TODO:
 * 输入一个逆波兰表达式(后缀表达式)，计算器结果
 * 支持小括号和多位<strong>整数</strong>
 *
 * TODO:
 * 抽时间研究下小数点匹配
 *
 * TODO:
 * 计划出一篇博客专门讲解逆波兰表达式
 *
 * @author 正义桑
 */
public class PolandNotation {
    public static void main(String[] args) {
        // 建立一个表达式
    //        String expression = "5+((1+20)*4)-3";
    //        List<String> infixExpressionList = convertInfixExpressionList(expression);
    //        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
    //        System.out.printf("结果为: %d", calc(suffixExpressionList));


        // 建立表达式
        // 例如 ： (30 + 4) x 5 - 6 ===转换===> 30 4 + 5 * 6 -
        // ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    //        String suffixExpression = "30 4 + 5 * 6 -";
        String suffixExpression = "10 6 9 3 + -11 * / * 17 + 5 +";
        List<String> lt = convert(suffixExpression);
        System.out.println("结果为:" + calc(lt));
    }

    /**
     * 转换为后缀表达式
     * @param infixExpression 输入的中缀表达式
     * @return 返回一个转换后的后缀表达式
     */
    public static List<String> parseSuffixExpressionList(List<String> infixExpression) {
        // 建立符号栈 s1
        Stack<String> s1 = new Stack<>();
        // 建立结果列表 s2
        List<String> s2  = new ArrayList<>();

        for (String item : infixExpression) {
            if (item.matches("\\d+")) {
                // 如果是数字
                s2.add(item);
            } else if (item.equals("(")) {
                // 如果是左括号 则入s1栈
                s1.push(item);
            } else if (item.equals(")")) {
                // 如果是右括号 则向下出栈，直至遇到(
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                // 丢弃左括号
                s1.pop();
            } else {
                // 如果是运算符
                // 如果运算符的优先级高于栈内的 则将栈内运算符移动至s2中
                while (s1.size() != 0 && (Operation.getValue(item) <= Operation.getValue(s1.peek()))) {
                    s2.add(s1.pop());
                }
                // 最后将运算符移动到符号栈中
                s1.push(item);
            }
        }
        // 将所有的剩余元素移动到s2中
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 将字符串表达式转换成中缀表达式列表
     * @param infixExpression 中缀表达式字符串
     * @return 返回中缀表达式列表
     */
    public static List<String> convertInfixExpressionList(String infixExpression) {
        int index = 0;
        char c;
        List<String> infixExpressionList = new ArrayList<>();
        while (infixExpression.length() > index) {
            c = infixExpression.charAt(index);
            if (c < 48 || c > 57) {
                // 如果字符为非数字
                infixExpressionList.add("" + c);
                index ++;
            } else {
                // 如果是数字
                StringBuilder num = new StringBuilder();
                while (infixExpression.length() > index && (c = infixExpression.charAt(index)) >= 48 && (c = infixExpression.charAt(index)) <= 57) {
                    // 遍历判断多位数
                    num.append(c);
                    index ++;
                }
                // 将数字存入列表
                infixExpressionList.add(num.toString());
            }
        }
        return infixExpressionList;
    }

    /**
     * 将表达式转换为列表
     * @param polandNotation 逆波兰表达式(后缀)
     * @return 表达式列表
     */
    public static List<String> convert(String polandNotation) {
        String[] strings = polandNotation.split(" ");
        // 将表达式转换为 列表
        List<String> lt = new ArrayList<>(Arrays.asList(strings));
        return lt;
    }

    /**
     * 计算表达式
     * @param list 输入一个表达式列表
     * @return 返回计算结果
     */
    public static int calc(List<String> list) {
        // 建立数栈
        Stack<Integer> numStack = new Stack<>();
        for (String item : list) {
            if (item.matches("^-?[0-9]+")) {
                // 匹配到整数 则直接入栈
                numStack.push(Integer.parseInt(item));
            } else {
                // 匹配到运算符 则计算
                int num2 = numStack.pop();
                int num1 = numStack.pop();
                int aws = 0;
                if (item.equals("+")) {
                    aws = num1 + num2;
                } else if (item.equals("-")) {
                    aws = num1 - num2;
                } else if (item.equals("*")) {
                    aws = num1 * num2;
                } else if (item.equals("/")) {
                    aws = num1 / num2;
                } else {
                    throw new RuntimeException("错误的运算符");
                }
                numStack.push(aws);
            }
        }
        return numStack.pop();
    }
}

/**
 * 运算符工具类
 * @author 正义桑
 */
class Operation {
    private final static int ADD = 1;
    private final static int SUB = 1;
    private final static int MUL = 2;
    private final static int DIV = 2;

    /**
     * 获取运算符优先级
     * @param operation 输入的运算符
     * @return 返回运算符优先级，如果没有则返回 -1
     */
    public static int getValue(String operation) {
        switch (operation) {
            case "+":
                return ADD;
            case "-":
                return SUB;
            case "*":
                return MUL;
            case "/":
                return DIV;
            default:
                System.out.printf("未知的运算符\"%s\"\n", operation);
                return -1;
        }
    }
}